package com.lans.SortAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;

/*
 * @author: lans
 * @date: 2025/1/10
 * @name: 刘宇
 * 基数排序复习
 */
public class BasicSort1 {
    public static int[] array = {112,31214,232,1213,7889,1233,22,1211,32,4};
    public static int[] sort(int[] array) {
        //1.创建桶
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
        for(int i=0;i<array.length;i++) {
            buckets.add(new ArrayList<>());
        }
        //2.找出最大值
        int max = array[0];
        for(int k:array){
            if(k>max){
                max=k;
            }
        }
        //3.计算最大值多少位
        int maxDigit=0;
        while(max!=0){
            max/=10;
            maxDigit++;
        }
        //4.将各个位数放入各个桶中
        int mold = 10;
        int div = 1;
        for(int i=0;i<maxDigit;i++,mold*=10,div*=10){
            for(int j:array){
                int num = (j%mold)/div;
                //放入对应桶中
                buckets.get(num).add(j);
            }
            //所有元素已经完成所有轮放桶 开始依次取出元素
            int index = 0;
            for(ArrayList<Integer> bucket:buckets){
                for(Integer num:bucket){
                    array[index++] = num;
                }
                bucket.clear();//清理桶
            }
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array1 = sort(array);
        System.out.println(Arrays.toString(array1));
    }
}
